/*
* 2010
* Authors: Dmitry Kolyanov <dk90.spb@gmail.com>, Ksenyia Cypan <ksenyiacypan@gmail.com>
*/

#include "stdafx.h"

const size_t max_group_num = 300;

/*
* nodes_type: 
*  weights.first <-----> black
* weights.second <-----> white
*/
std::pair<w_size_type, w_size_type> maxcut::intermidiate_edges_weight(Vertex v, size_t  group_number, const Graph &g)
{
	std::pair<w_size_type, w_size_type> weights(0,0);

	graph_traits<Graph>::out_edge_iterator e1, e1_end;
	for(tie(e1 ,e1_end) = out_edges(v, g); e1 != e1_end; ++e1)
	{
		if(vertices_group_nums[target(*e1, g)] == group_number)
		{
			if(is_black(target(*e1,g), g)) 
				weights.first += get(edge_weight, g, *e1);
			else
				weights.second += get(edge_weight, g, *e1);
		}
	}

	return weights;
}


size_t maxcut::best_group_arg(size_t groups_size, Vertex v, size_t group_number, Graph &g)
{
	size_t arg_max = 0;
	w_size_type max = 0, tmp_max;
	std::pair<w_size_type, w_size_type> weights;
	for(size_t j = 0;  j < groups_size;  j++)
	{
		if(j == group_number)
			continue;

		weights = intermidiate_edges_weight(v, j, g);
		tmp_max = std::max(weights.first, weights.second);

		if(max < tmp_max)
		{
			max = tmp_max;
			arg_max = j;
		}
	}
	weights = intermidiate_edges_weight(v, arg_max, g);
	if(weights.first > weights.second)
		paint_white(v, g);
	else
		paint_black(v, g);

	return arg_max;
}

void maxcut::loser_strategy(size_t group_number, Graph &g)
{
	size_t groups_size = groups.size();
	size_t arg_max = 0;

	for(Group::iterator vi = groups[group_number].first->begin(); vi != groups[group_number].first->end(); ++vi)
	{
		arg_max = best_group_arg(groups_size, *vi, group_number, g);
		if(arg_max != group_number)
		{
			groups[arg_max].first->push_back(*vi);
			vertices_group_nums[*vi] = arg_max;
		}
	}
	groups[group_number].first->clear();
}


void maxcut::winner_strategy(size_t group_number, Graph &g)
{
	std::pair<w_size_type, w_size_type> weights;

	for(Group::iterator vi = groups[group_number].first->begin(); vi != groups[group_number].first->end(); ++vi)
	{
		weights = intermidiate_edges_weight(*vi, group_number, g);

		if(is_black(*vi, g) && weights.first > weights.second)
			paint_white(*vi, g);
		if(is_white(*vi, g) && weights.first < weights.second)
			paint_black(*vi, g);
	}	
}

void maxcut::create_initial_groups(Graph &g)
{
	size_t vertices_in_group = 1;
	size_t num_v = num_vertices(g);

	if(num_v > max_group_num)
		vertices_in_group = (size_t)(num_v/max_group_num);


	Obj_group pair(new Group(), 0);
	int i = 0;

	graph_traits<Graph>::vertex_iterator v, v_end;
	for(tie(v, v_end) = vertices(g); v != v_end; ++v)
	{
		if(i % vertices_in_group == 0 && i != 0)
		{
			if(groups.size() != max_group_num - 1)
			{
				groups.push_back(pair);
				pair.first = new Group();
			}
		}
		pair.first->push_back(*v);
		paint_black(*v, g);
		vertices_group_nums[*v] = i % vertices_in_group;
		i++;
	}
	groups.push_back(pair);	
};

w_size_type maxcut::group_weight(Community::iterator group, const Graph &g){
	w_size_type weight = 0;
	graph_traits<Graph>::out_edge_iterator e1, e1_end;
	for(Group::iterator gi = group->first->begin(); gi != group->first->end(); ++gi)
	{
		for(tie(e1 ,e1_end) = out_edges(*gi,g); e1 != e1_end; ++e1)
		{
			if( is_varigated(*e1, g)  && vertices_group_nums[target(*e1, g)] == std::distance(groups.begin(), group))
				weight += get(edge_weight, g, *e1);
		}
	}
	return weight;
}

void maxcut::update_groups(const Graph &g)
{
	Community updated_groups;

	for(Community::iterator group = groups.begin(); group != groups.end(); ++group)
	{
		if(group->first->size() > 0)
			updated_groups.push_back(Obj_group(group->first, group_weight(group, g)/2));
		else
			delete group->first;
	}
	updated_groups.swap(groups);
}

size_t maxcut::max_weight_group()
{
	w_size_type max = 0;
	size_t arg_max = 0;
	for(Community::iterator group = groups.begin(); group != groups.end(); ++group)
	{
		if(max < group->second)
		{ 
			max = group->second;
			arg_max = std::distance(groups.begin(), group);
		}
	}
	return arg_max;
}

void maxcut::genetic_algorithm(Graph &g)
{
	if(num_vertices(g) != 0)
	{
		create_initial_groups(g);

		bool winner_phase = false;

		while(groups.size() > 1 || winner_phase)
		{
			update_groups(g);
			std::cout<<"groups.size"<<groups.size()<<"\n";
			/*
			int p=0;
			for(Community::iterator group = groups.begin(); group != groups.end(); ++group){
			std::cout<<"group"<<p<<"\n";
			for(Group::iterator gi = group->first->begin(); gi != group->first->end(); ++gi)
			{
			if(is_black(*gi, g))
			std::cout<<"vertex: "<<*gi<<" is black"<<"\n";
			else
			std::cout<<"vertex: "<<*gi<<" is white"<<"\n";
			}
			std::cout<<"-----------------------------------\n";
			p++;
			}
			*/
			winner_phase |= (groups.size() == 1);

			for (size_t i = 0; i < groups.size(); i++)
			{
				if(i == max_weight_group() || winner_phase)
					winner_strategy(i, g);			
				else
					loser_strategy(i, g);
			}

			winner_phase = !winner_phase;
		}

		maxcut_size = groups[0].second;
		delete groups[0].first;
	}
}